#include<stdio.h>
const int maxn=20190324;
int main()
{
	int a=1,b=1,c=1,n;
	for(int i=4;i<=20190324;i++){
		n=(a+b+c)%10000;
		a=b;
		b=c;
		c=n;
	}
	printf("%d",n);
	return 0;
}
